<?php

namespace liketp\foundation;

class PriorityQueue
{
    protected $queue = [];

    public function isEmpty()
    {
        return empty($this->queue);
    }

    public function count()
    {
        return count($this->queue);
    }

    public function top()
    {
        return $this->isEmpty() ? null : $this->queue[0];
    }

    public function insert($item, $priority)
    {
        $item['_priority'] = $priority;

        $index = $this->getPrioritySlot($priority);

        if ($index === false) {
            array_unshift($this->queue, $item);
        } else {
            array_splice($this->queue, $index, 1, [$this->queue[$index], $item]);
        }
    }

    public function extract()
    {
        $item = array_shift($this->queue);
        return $item;
    }

    public function remove($priority)
    {
        $index = $this->getPriorityIndex($priority);

        if ($index === false) return;

        array_splice($this->queue, $index, 1);
    }

    public function clear()
    {
        $this->queue = [];
    }


    //------------------------------------------------ protected
    protected function getPriorityIndex($priority, $completeEqual = true)
    {
        if ($this->isEmpty()) return false;

        $min = 0;
        $max = $this->count() - 1;

        while (true) {
            $index = floor(($max - $min) / 2) + $min;

            $item = $this->queue[$index];

            if ($max - $min <= 1) {
                // get index
                if ($completeEqual) {
                    if ($this->queue[$max]['_priority'] == $priority) {
                        return $max;
                    } else if ($this->queue[$min]['_priority'] == $priority) {
                        return $min;
                    } else {
                        return false;
                    }
                }
                // get slot index
                else {
                    if ($this->queue[$max]['_priority'] <= $priority) {
                        return $max;
                    } else if ($this->queue[$min]['_priority'] <= $priority) {
                        return $min;
                    } else {
                        return false;
                    }
                }
            }

            if ($priority < $item['_priority']) {
                $max = $index;
            } else {
                $min = $index;
            }
        }
    }

    protected function getPrioritySlot($priority)
    {
        return $this->getPriorityIndex($priority, false);
    }
}
